(a) Field
Aspects of embodiments of the present invention relate to an elimination method for common sub-expression.
(b) Description of the Related Art
In many situations, high-speed finite impulse response (FIR) filters need to be operated with low power using CMOS technology in mobile communication terminals. Regarding such filters, studies on implementations of filter coefficients represented as canonical signed digit (CSD) numbers in which the number of 1's and −1's is less than the number of 1's in the two's complement representation has been actively undertaken.
Structures in which multiplication is processed using only adders, subtractors, shifters, and delay elements in high-speed/low power filters are desired. Such structures may benefit from CSD-type coefficients, which have fewer nonzero digits than comparable two's complement coefficients.
For an N-bit number, the two's complement may be represented as
            ∑              i        =        0                    N        -        1              ⁢                  a        i            ⁢              2        i              ,where aN-1=0 or −1 and ai=0 or 1 for i<N−1. The CSD representation is similar, only each ai=1, 0, or −1, with no two consecutive ai taking on nonzero values. Binary numbers in two's complement may be represented in CSD by repeatedly replacing strings of consecutive nonzero digits with equivalent strings having only nonconsecutive nonzero digits. Hereinafter, −1 will be represented as n for convenience of description. Then, 01111 in two's complement is represented as 1000n in CSD. A binary number in two's complement may be easily converted to a number in CSD as described above, and all binary numbers in two's complement may be represented as numbers in CSD.
In contrast to a number in two's complement, the most number of nonzero digits in an N-digit CSD number is (N+1)/2, and this implies that the number of adders (or subtractors) may be reduced in multiplication implementations using CSD numbers. Multiplication of the filter coefficients may be implemented using addition and shift operations, which are easily implemented using hardwired logic. That said, studies and research efforts have focused on reduction of the number of additions by using CSD numbers.
However, when CSD is used for linear-phase filter coefficients, additional memory may be needed (e.g., to store the sign of each digit) so that the size of hardware and manufacturing expense may not be minimized.
The above information disclosed in this Background section is only for enhancement of understanding of the background of the invention and therefore it may contain information that does not form the prior art that is already known in this country to a person of ordinary skill in the art.